package com.ruoyi.common.utils;


/**
 * @description:路由图工具类
 * @author: net
 * @create: 2024-12-01 22:47
 **/
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class GraphUtil {
    public static class Graph{
        private final int vertices;
        private List<List<Integer>> adjacencyList;
        public Graph(int vertices) {
            this.vertices = vertices;
            adjacencyList = new ArrayList<>(vertices);
            for (int i = 0; i < vertices; i++) {
                adjacencyList.add(new ArrayList<>());
            }
        }

        public void addEdge(int source, int destination) {
            adjacencyList.get(source).add(destination);
        }

        /**
         * 返回起止点所有的线路
         * @param source
         * @param destination
         * @return
         */
        public List<List<Integer>> allPathsSourceToDestination(int source, int destination) {
            boolean[] visited = new boolean[vertices];
            List<List<Integer>> paths = new ArrayList<>();
            List<Integer> path = new ArrayList<>();
            dfs(source, destination, visited, path, paths);
            return paths;
        }

        private void dfs(int source, int destination, boolean[] visited, List<Integer> path, List<List<Integer>> paths) {
            visited[source] = true;
            path.add(source);

            if (source == destination) {
                paths.add(new ArrayList<>(path));
            } else {
                for (int neighbor : adjacencyList.get(source)) {
                    if (!visited[neighbor]) {
                        dfs(neighbor, destination, visited, path, paths);
                    }
                }
            }

            visited[source] = false;
            path.remove(path.size() - 1);
        }
    }




    /**
     * 线路分割为线段集合
     * @param route
     * @return
     */
    public static List<List<String>> cutRouteToLine(List<String> route){
        List<List<String>> afterCutLines = new ArrayList<>();
        for (int i = 0; i <route.size()-1 ; i++) {
            afterCutLines.add(Arrays.asList(route.get(i),route.get(i+1)));
        }
        return afterCutLines;
    }
    /**
     * 二维数组中取两个最短长度的数组
     */
    public static List<List<String>>  findTwoShortestArrays(List<List<String>> arrays) {
        List<List<String>> listList =new ArrayList<>();
        if (arrays == null || arrays.size() < 2) {
            System.out.println("做比较的数组只有一条，直接返回该数组");
            return arrays;
        }

        int minLength1 = Integer.MAX_VALUE;
        int minLength2 = Integer.MAX_VALUE;
        List<String> shortestArray1 = null;
        List<String> shortestArray2 = null;

        for (List<String> array : arrays) {
            int length = array.size();

            if (length < minLength1) {
                minLength2 = minLength1;
                shortestArray2 = shortestArray1;
                minLength1 = length;
                shortestArray1 = array;
            } else if (length < minLength2) {
                minLength2 = length;
                shortestArray2 = array;
            }
        }

        System.out.println("The two shortest arrays are:");
        System.out.println("最短路径: " + shortestArray1.toString());
        System.out.println("次最短路径: " +shortestArray2.toString() );
        listList.add(shortestArray1);
        listList.add(shortestArray2);
        return listList;
    }
   /* public static void main(String[] args) {
        Graph graph = new Graph(5);
        graph.addEdge(0, 1);
        graph.addEdge(0, 4);
        graph.addEdge(1, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 4);
        graph.addEdge(3, 4);

        List<List<Integer>> paths = graph.allPathsSourceToDestination(0, 4);
        for (List<Integer> path : paths) {
            System.out.println(path);
        }
    }*/
       public static void main(String[] args) {
           //2,3,4,5 取23  2234 取22 2334 取23
           String[][] arrays = {
                   {"a", "b", "c"},
                   {"d", "e"},
                   {"f","a","f","a","y"},
                   {"g", "h", "i", "j"}
           };

           findTwoShortestArrays(arrays);
       }

       public static void findTwoShortestArrays(String[][] arrays) {
           if (arrays == null || arrays.length < 2) {
               System.out.println("The input array does not contain enough subarrays.");
               return;
           }

           int minLength1 = Integer.MAX_VALUE;
           int minLength2 = Integer.MAX_VALUE;
           String[] shortestArray1 = null;
           String[] shortestArray2 = null;

           for (String[] array : arrays) {
               int length = array.length;

               if (length < minLength1) {
                   minLength2 = minLength1;
                   shortestArray2 = shortestArray1;
                   minLength1 = length;
                   shortestArray1 = array;
               } else if (length < minLength2) {
                   minLength2 = length;
                   shortestArray2 = array;
               }
           }

           System.out.println("The two shortest arrays are:");
           System.out.println("最短路径: " + java.util.Arrays.toString(shortestArray1));
           System.out.println("次最短路径: " + java.util.Arrays.toString(shortestArray2));
       }

}
